{
  // 算法题：
  let data = [
    { id: 1, parentId: 0 },
    { id: 2, parentId: 1 },
    { id: 3, parentId: 1 },
  ];

  // 要求把这个数组从顶级分类递归查找子分类，最终构建一个树状数组。结果必须输出如下
  // parentId为0 的是根节点
  const res = [
    {
      id: 1,
      parentId: 0,
      children: [
        { id: 2, parentId: 1 },
        { id: 3, parentId: 1 },
      ],
    },
  ];

  // 实现方式如下
  function handleTree(arrs = []) {
    let treeData = {};
    treeData = arrs.reduce((lastItem, item) => {
      if (item.parentId == 0) {
        return {
          ...item,
          children: [],
        };
      }
      lastItem.children.push(item);
      return lastItem;
    }, {});
    return [treeData];
  }
  const res = handleTree(data);
  console.log(JSON.stringify(res));

  // 答案
  var nodes = [
    { id: 1, pId: 0, name: '父节点1 - 展开', open: true },
    { id: 11, pId: 1, name: '父节点11 - 展开', open: true },
    { id: 111, pId: 11, name: '父节点111 - 折叠' },
    { id: 112, pId: 11, name: '父节点112 - 折叠' },
    { id: 12, pId: 1, name: '父节点12 - 折叠' },
    { id: 13, pId: 1, name: '父节点13 - 没有子节点' },
    { id: 2, pId: 0, name: '父节点2 - 折叠' },
    { id: 21, pId: 2, name: '父节点21 - 展开', open: true },
    { id: 22, pId: 2, name: '父节点22 - 折叠' },
    { id: 23, pId: 2, name: '父节点23 - 折叠' },
    { id: 3, pId: 0, name: '父节点3 - 没有子节点' },
  ];

  function listToTree(data, options) {
    options = options || {};
    var ID_KEY = options.idKey || 'id';
    var PARENT_KEY = options.parentKey || 'pId';
    var CHILDREN_KEY = options.childrenKey || 'children';

    var tree = [],
      childrenOf = {};
    var item, id, parentId;

    for (var i = 0, length = data.length; i < length; i++) {
      item = data[i];
      id = item[ID_KEY];
      parentId = item[PARENT_KEY] || 0;
      childrenOf[id] = childrenOf[id] || [];
      item[CHILDREN_KEY] = childrenOf[id];
      if (parentId != 0) {
        childrenOf[parentId] = childrenOf[parentId] || [];
        console.info(parentId);
        childrenOf[parentId].push(item);
      } else {
        tree.push(item);
      }
    }

    return tree;
  }

  const tree = listToTree(nodes);
}

// 去掉⼀一个数组中的重复项，并按升序排序。
{
}

// Array数组的flat⽅方法实现(2018⽹网易易雷雷⽕火&伏羲前端秋招笔试)
{
  // Array的⽅方法flat很多浏览器器还未能实现，请写⼀一个flat⽅方法，实现扁平化嵌套数组，如
  var arr1 = [1, 2, [3, 4]];
  arr1.flat(Infinity); // [1, 2, 3, 4]
}

// 题⽬目描述：开⼼心消消乐；
/* 
给定一个一维的正整数数组，逐次选择其中⼀个数做消除，消除所获得的分数为当前数字和左右相邻数
字的乘积（当左边或者右边没有数字可以认为是1）。 e.g. 输⼊入数组：[3, 1, 5, 8] 
step1：消除1 ，获得分数 15 = 3x1x5，数组变为 [3, 5, 8] 
step2：消除5，获得分数 120 = 3x5x8，数组变为 [3, 8] 
step3：消除3，获得分数 24 = 3x8，数组变为[8] 
step4：消除8，获得分数 8 = 8，数组变为[] 
最终获得分数：15+120+24+8 = 167 求消除能够获取的最⼤大分数
*/
{
}

/* 
输⼊入⼀个自定义的数组，例如1,4,5,23,2,17,24,10000000。请把他按照中间⾼高两边低进行排序，最后的结果是1,4,5,23,10000000,24,17,2，算法越准确越好，请注意左右翼数据数据的平衡性。
*/
{
}

// 在⼀个二维数组中，每⼀一⾏行行都按照从左到右递增的顺序排序，每⼀列列都按照从上到下递增的顺序排序。请完成一个函数，输⼊入这样的⼀个二维数组和一个整数，判断数组中是否含有该整数。
{
  /* 
  输⼊入输出分析 每当拿到⼀个算法题的时候，不不要脑⼦子中稍微有点思路路后，就开始写代码。⽽而是先把题⽬目
  中规定的参数搞清楚，然后把参数的例子写出来。
  本题两个参数举例例：
  1. 递增二维数组

  1 2 8 9
  2 4 9 12
  4 7 10 13
  6 8 11 15

  注意 题⽬目只说每⼀一⾏行行是递增的，没有说增幅是多少，不不要以为增幅是1。同时也没有说⾏行行数和列列数相等
  2. 要查找的整数 ⽐比如：7、5、0、16
  对应的输出结果：true、false、false、false
  */
}

/* 
二数之和，给定一个整数数组和一个目标值，找出数组中和为目标值的两个数，
你可以假设每个输出对应一种答案，且同样元素不能重复被利用
*/
{
  const _nums = [2, 7, 11, 15];
  const _target = 9;
  function resultNum(nums = [], target) {} // 返回[0, 1]

  // 实现方法如下：
  function resultNum(nums = [], target) {
    let hashMap = new Map();
    const len = nums.length;
    let diff;
    for (let i = 0; i < len; i++) {
      diff = target - nums[i];
      if (hashMap.has(diff)) {
        return [hashMap.get(diff), i];
      }
      hashMap.set(nums[i], i);
    }
  }
  console.log(resultNum(_nums, _target));

  // 题目二：输入一个递增排序的数组和一个数字s，在数组中查找二个数使得正好是s，如果有多个和相等于，则输出任意一对即可。
  const _nums = [2, 7, 11, 15];
  const _target = 9; // 查找后输出[2, 7] 或 [7, 2]

  /* 实现解析
  准备二个指针 left开始指针， right指向数组结尾
  如果二指针相加的和等于target，那么直接返回相应的值
  如果二指针相加的和大于target，此时应该缩小范围，所以right指针--向左移
  如果二指针相加的和小于target，此时left指针缩小范围，--向右移
  */
  function resultNum(nums = [], target) {
    let left = 0,
      right = nums.length - 1;
    while (left < right) {
      if (nums[left] + nums[right] > target) {
        --right;
      } else if (nums[left] + nums[right] < target) {
        --left;
      } else {
        return [nums[left], nums[right]];
      }
    }
  }
  console.log(resultNum(_nums, _target));
}

/* 
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增和顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否包含有该整数。
*/
{
  let arr = [
    [1, 3, 7, 11, 15],
    [2, 5, 8, 12, 19],
    [3, 6, 9, 16, 22],
    [10, 13, 14, 17, 24],
  ];

  // 解答实现：
  function findArr(arrs, num) {
    if (!Number.isInteger(num)) {
      console.log('非整数');
      return false;
    }

    const arrLen = arr.length;
    let res = false;
    for (let i = 0; i < arrLen; i++) {
      if (new RegExp(num, 'g').test(JSON.stringify(arrs[i]))) {
        res = true;
        break;
      }
    }
    return res;
  }

  console.log(findArr(arr, 16));

  // 实现方法二：
  function findNumberIn2DArray(matrix = [], target) {
    if (!Number.isInteger(target) || matrix.length == 0) return false;
    return new RegExp('[\\[,\\]]' + target + '[\\[\\],]', 'g').test(
      String(matrix)
    );
  }
}

/* 
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）
f(n) = f(n - 1) + f(n - 2)

解题提示:
1、基本解法是递归、注意避免递归的缺陷
2、可以试试动态规划解法
*/
{
  function fibonacci(n) {}
  console.log(fibonacci(45));

  // 实现如下
  var fib = function (n) {
    if (n <= 1) return n < 0 ? false : n;
    let fibArr = [1, 1];
    let currentNum = 1; // 当前值
    let lastNum = 1; // 上一个值
    let resNum;

    switch (true) {
      case n > 30 && n < 50:
        currentNum = 832040;
        lastNum = 514229;
        fibArr = [...','.repeat(30)];
        break;
      case n > 50 && n < 100:
        currentNum = 12586269025;
        lastNum = 7778742049;
        fibArr = [...','.repeat(50)];
        break;
      case n > 100 && n < 300:
        currentNum = 354224848179261915075;
        lastNum = 218922995834555169026;
        fibArr = [...','.repeat(100)];
        break;
    }
    for (let i = 2; i <= n; i++) {
      let _i = fibArr.push((currentNum + lastNum) % 1000000007) - 1;
      lastNum = currentNum;
      currentNum = fibArr[_i];
      if (n == _i) {
        resNum = fibArr[_i - 1];
        break;
      }
    }

    return resNum;
  };

  // 实现版本二：通过斐波那契通用公式实现，不过数值大了，因为精度问题会算的不是完全准确
  const fibonacci = (num) => {
    const sqrt5 = Math.sqrt(5);
    const left = Math.pow((1 + sqrt5) / 2, num);
    const right = Math.pow((1 - sqrt5) / 2, num);
    return Math.floor((left - right) / sqrt5);
  };
}

//  统计一个数字在排好序的数组中出现的次数
// 提示：本题目有多种解法，试着分析哪种解法更好
{
}

/* 
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如字符串"+100","5e2","-123","3.1416","-1E-16"都表示数值。
但是"12e","1a3.14","1.2.3","+-5","12e+4.3"都不是
*/
{
  let numData = [
    '+0',
    '-0',
    '0',
    '+100',
    '5e2',
    '-123',
    '3.1416',
    '-1E-16',
    '0123',
    '9007199254740991n',
  ];
  let noNumData = [
    '12e',
    '1a3.14',
    '1.2.3',
    '+-5',
    '12e+4.3',
    '12e+4.3n',
    '12en',
  ];

  // 实现方法
  function isNumFn(num) {
    try {
      if (/n$/g.test(num)) {
        const _rpNum = +num.replace('n', '');
        return BigInt(_rpNum) == _rpNum || !isNaN(_rpNum);
      }
      return !isNaN(num);
    } catch (error) {
      return false;
    }
  }

  for (let i = 0; i < noNumData.length; i++) {
    console.log(isNumFn(noNumData[i]));
  }
}

// 把一维数组做成二维数组,并且按指定切块数量
{
  let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
  // 输出结果 [[1,2,3,4],[5,6,7,8],[9,10]]
}

// 要求把如下数据转成另一个格式
{
  let list = [
    {
      parent_ind: '女装',
      name: '连衣裙',
    },
    {
      name: '女装',
    },
    {
      parent_ind: '女装',
      name: '半身裙',
    },
    {
      parent_ind: '女装',
      name: 'A字裙',
    },
    {
      name: '数码',
    },
    {
      parent_ind: '数码',
      name: '电脑配件',
    },
    {
      parent_ind: '电脑配件',
      name: '内存',
    },
  ];
  // 输出如下结果
  const res = {
    数码: {
      电脑配件: {
        内存: {},
      },
    },
    女装: {
      连衣裙: {},
      半身裙: {},
      A字裙: {},
    },
  };
}

// 怎么给数组去重，能使用几种方法去重？
{
  let arr = [1, 23, 4, 3, 6, 7, 8, 1, 4, 1, 3, 6];
  // 第一种通过set方法实现去重
  const onlyArr1 = new Set(arr);
  console.log([...onlyArr1]);

  // 第二种通过map对象过滤去重数组
  const arrMap = {};
  let onlyArr2 = [];
  arr.forEach((item) => {
    arrMap[item] = item;
  });
  for (const item in arrMap) {
    onlyArr2.push(item);
  }
  console.log(onlyArr2);

  // 第三种  创建一个新数组。。。循环老的数组。。判断新数组中 是否有  老数组[i]，没有就插入
  let onlyArr3 = [];
  arr.forEach((item) => {
    if (!onlyArr3.includes(item)) {
      onlyArr3.push(item);
    }
  });
  console.log(onlyArr3);

  // 第四种。。使用reduce。。。同理。。当前返回的值判断是否在reduce当中，如果是，不返回
  let onlyArr4 = [];
  arr.reduce((prev, curr) => {
    if (!onlyArr4.includes(curr)) {
      onlyArr4.push(curr);
    }
  }, []);
  console.log(onlyArr4);
}

// [2,6,3,8,10,9]  返回一个数组，找到每个元素右侧第一个比它大的数字，没有的话返回-1   [6,8,8,10,-1,-1]
{
}

// 根据ID快速找到对应的元素
{
  const tree = {
    id: 'root',
    children: [
      { id: 1, children: ['id1'] },
      { id: 2, children: ['id2'] },
      { id: 3, children: ['id3'] },
      {
        id: 4,
        children: [{ id: 5, children: ['id4的id5'] }],
      },
      {
        id: 6,
        children: [
          {
            id: 7,
            children: [{ id: 8, children: ['id4的id5'] }],
          },
        ],
      },
    ],
  };

  // 定义封装查询数据的方法
  function search(id, node) {
    // 容错层，没有节点直接出错
    if (!node.children) return null;
    // 循环children节点
    for (const nodeItemChild of node.children) {
      if (nodeItemChild.id === id) {
        return nodeItemChild;
      } else {
        // 一定要保存最后递归的数据，不然不能正常返回查找到的数据
        let same = search(id, nodeItemChild);
        if (same) return same;
      }
    }
  }

  var result = search(5, tree);
  console.log(result); // 为{id: 5, children: Array(1)}
}

// 输入两个字符串 2018-08  2018-12 输出他们中间的月份 [2018-10, 2018-11]
{
  function dateStrFn(startDateStr, endDateStr) {
    const _start = new Date(startDateStr);
    const _end = new Date(endDateStr);
    // 月份字典
    const month = [
      '01',
      '02',
      '03',
      '04',
      '05',
      '06',
      '07',
      '08',
      '09',
      '10',
      '11',
      '12',
    ].reduce((lastItem, value, key) => {
      lastItem[key] = value;
      return lastItem;
    }, {});

    // 月份时间戳
    const monthTime =
      new Date('2018-08').getTime() - new Date('2018-09').getTime();

    let tempDate; // 临时时间变量
    let resultTime = [];

    // 计算年、月，总累计月数
    let forIndex =
      Math.ceil((_start.getTime() - _end.getTime()) / monthTime) - 1;

    for (let i = 0; i < forIndex; i++) {
      tempDate = new Date(startDateStr); // 归0_start初始
      tempDate.setMonth(_start.getMonth() + i + 1);
      resultTime.push(
        `${tempDate.getFullYear()}-${month[tempDate.getMonth()]}`
      );
    }

    return resultTime;
  }

  console.log(dateStrFn('2018-08', '2018-11')); // 输出[2018-10, 2018-11]
}

// 判断一个字符串中出现次数最多的字符，统计这个次数
{
  let str = 'sdfjjjjjjklsssssssl';

  // 答：通过拆成数组，var newArr = str.split('')
  // 建立一个对象存放json=[]、循环数组把值和数字存进入key(字符串名)-value(出现次数)
  for (i = 0; i < newArr.length; i++) {
    if (json[newArr[i]]) {
      json[newArr[i]] += 1;
    } else {
      json[newArr[i]] = 1;
    }
  }
  // 最后在把对象循环一次对比最大的输出
  var num = 0,
    number = '';
  for (key in json) {
    if (json[key] > num) {
      num = json[key];
      number = key; // 存放哪个字符是最多的
    }
  }
}

// 转换entry数据成指定数据结构输出
{
  let entry = {
    a: {
      b: {
        c: {
          dd: 'abcdd',
        },
      },
      d: {
        xx: 'adxx',
      },
      e: 'ae',
    },
  };
  // 要求转换成如下对象
  let output = {
    'a.b.c.dd': 'abcdd',
    'a.d.xx': 'adxx',
    'a.e': 'ae',
  };

  // 具体实现代码
  function outputFn(params) {
    let endData = {};
    if (params.constructor === Object) {
      let _key = '';
      for (const key in params) {
        if (params.hasOwnProperty(key)) {
          _key += _key ? `.${key}` : key;
          switch (params[key].constructor) {
            case Object:
              endData = { ...endData, ...outputFn(params[key]) }; // 递归
              break;
            case String:
              endData[_key] = params[key];
            default:
              break;
          }
        }
      }
    }
    return endData;
  }
  console.log(outputFn(entry));
}

// 扁平化数组成一维数组
{
  var arr1 = [1, 2, [3, [4, 5, [6], 7]], 8, 9];
  arr1.flat(Infinity); // 方式一
  // 方式二
  function flatten(arr = []) {
    return arr.reduce((lastItem, item) => {
      return Array.isArray(item)
        ? [...lastItem, ...flatten(item)]
        : lastItem.concat(item);
    }, []);
  }
  console.log(flatten(arr1));

  // 方式三：
  function flatDeep(arr) {
    let str = JSON.stringify(arr);
    str = str.replace(/[\[\]]/g, '');
    return str.split(',').map((v) => +v);
  }
  console.log(flatDeep(arr1));
}

// 实现如下效果，函数式编辑思想，颗粒化
{
  console.log(fn(1));
  console.log(fn(1, 2));
  console.log(fn(1, 2)(3));
  console.log(fn(1, 2)(3)(4)); // 10

  // 以下实现逻辑代码
  function curry(fn, ...allArgs) {
    // 只有参数和num函数相等情况下，才会返回计算的值
    return allArgs.length >= fn.length
      ? fn(...allArgs) // 调用最终num函数，计算返回值
      : (...arg) => curry(fn, ...allArgs, ...arg); // 递归传递参数
  }

  const num = (a, b, c, d) => {
    return a + b + c + d;
  };
  const fn = curry(num);
}

// 求字符串数组的最长公共前缀
// 比如输入: ["flower","flow","flight"]，输出: "fl"
{
  let strArr = ['flower', 'flow', 'flight'];

  // 解题思路是先获取数组中的最大值及最小值字符串，最小字符串与最大字符串的最长公共前缀也为其他字符串的公共前缀，即为字符串数组的最长公共前缀
  var longestCommonPrefix = function (strs) {
    if (strs === null || strs.length === 0) return '';
    if (strs.length === 1) return strs[0];
    let min = 0,
      max = 0;
    for (let i = 1; i < strs.length; i++) {
      if (strs[min] > strs[i]) min = i;
      if (strs[max] < strs[i]) max = i;
    }
    for (let j = 0; j < strs[min].length; j++) {
      if (strs[min].charAt(j) !== strs[max].charAt(j)) {
        return strs[min].substring(0, j);
      }
    }
    return strs[min];
  };

  console.log(longestCommonPrefix(strArr));
}

// 输入一个链表，反转链表后，输出新链表的表头
{
  /* 
  解法思路：
  借助栈的后入先出顺序，可以将顺序列表逆序。不过这不是原地反转，当然题目也没有要求。
  处理过程如下：
  从头到尾遍历链表，将节点val依次放入栈，从栈中依次取出val，构造新节点，并连接节点

  时间复杂度O(n)，空间复杂度O(n)，代码如下：
  */
  let reverseList = function (head) {
    if (!head) return null;
    const stack = [];
    let node = head;
    while (node) {
      stack.push(node.val);
      node = node.next;
    }

    const newHead = {
      val: stack.pop(),
      next: null,
    };
    node = newHead;

    while (stack.length) {
      node.next = {
        val: stack.pop(),
        next: null,
      };
      node = node.next;
    }
    return newHead;
  };
}

// 实现multiply方法，返回如下格式的值
{
  Array.prototype.multiply = function () {}; // 实现
  var a = [1, 2, 3, 4, 5];
  a.multiply();
  console.log(a); // 输出如下 [1, 2, 3, 4, 5, 1, 4, 9, 16, 25]

  // 实现方法如下
  Array.prototype.multiply = function () {
    var arr = this;
    if (typeof arr !== 'object') return null;
    console.log(typeof arr);
    return arr.reduce(function (lastItem, item) {
      lastItem.push(item * item);
      return lastItem;
    }, arr);
  };
}

// 实现getProperty方法，获取对象上面指定的属性值，如果没有返回undefined
{
  function getProperty(obj, str) {} // 实现
  var obj = { a: { b: { c: 1 } } };
  let d1 = getProperty(obj, 'a.b.c'); // 1
  let d2 = getProperty(obj, 'aa.d.c'); // undefined 不报错
  console.log(d2);

  // 实现代码如下：
  function getProperty(obj, str) {
    if (obj === null || str === null) return undefined;
    try {
      var getObj = str.split('.');
      return getObj.reduce(function (lastItem, item) {
        return lastItem[item];
      }, obj || {});
    } catch (error) {
      return undefined;
    }
  }
}

// 二个大整数相加返回结果字符串，题目使用es5方法
{
  function add(a, b) {}
  var o = add('23429512132347622325', '0228292272494125684241');
  console.log(o);

  /* 
  解题思路：通过切割字符串成数组，让二个a,b值长度一样，不足的前缀补0。
  如果是直接切割数组的话，就是一个字符串切割一个，要是需要优化此处切割还需要处理一次，根据定好的切割长度，进行无限循环，从字符串尾部开始截取生成数组（一次性操作a,b二个，长度是一样的）

  接着循环切割出来的数组，倒序循环从尾部开始，通过求余值直接赋值当前循环的i值，并且如果求余等于0的时候，对数组前一位进行+1操作。这一系列操作只需要在aar1或aar2一个数组中操作就行了。

  最后进行收尾操作，把切割计算好的数组进行join转成字符串，在判断第一个字符串如果是0，截取掉第一个值，否则正常返回即可。

  PS：常规单个切割性能有点差，如果进行指定长度切割，大大提高计算性能速度
  */

  // 常规切割实现
  function add(str1, str2) {
    // 补全0，并多补一位0
    let arr1 = null,
      arr2 = null;
    if (str1.length > str2.length) {
      str1 = '0' + str1;
      for (let i = str2.length; i < str1.length; i++) {
        str2 = '0' + str2;
      }
      arr1 = str1.split('');
      arr2 = str2.split('');
    } else {
      str2 = '0' + str2;
      for (let i = str1.length; i < str2.length; i++) {
        str1 = '0' + str1;
      }
      arr1 = str1.split('');
      arr2 = str2.split('');
    }
    // 注意这里arr里边保存的还是字符串，需要转成数字后再相加
    for (let i = arr1.length - 1; i >= 0; i--) {
      let temp = parseInt(arr1[i]) + parseInt(arr2[i]);
      arr1[i] = temp % 10;
      // 处理得到进位的结果
      arr1[i - 1] = parseInt(arr1[i - 1]) + Math.floor(temp / 10);
    }
    if (arr1[0] === 0) {
      return arr1.join('').substring(1);
    } else {
      return arr1.join('');
    }
  }

  // 切割指定长度，提升性能，不过相对就会引起一些bug取余正好四位数的，会计算不正确
  function add(a, b) {
    // 补全0，并多补一位0
    let arr1 = [],
      arr2 = [],
      fillStr = '0',
      spSum = 4,
      temp = null,
      abLen = a.length - b.length;

    if (abLen < 0) {
      b = fillStr + b;
      for (let i = 0; i < Math.abs(abLen) + 1; i++) {
        a = fillStr + a;
      }
    } else {
      a = fillStr + a;
      b = fillStr + b;
    }

    // 切割成数组，按指定长度字符串切割
    let lastIdx = a.length,
      start = 0;
    while (lastIdx > 0) {
      if (lastIdx < spSum) {
        arr1.unshift(a.slice(0, lastIdx));
        arr2.unshift(b.slice(0, lastIdx));
        break;
      }
      start = lastIdx - spSum;
      arr1.unshift(a.slice(start, lastIdx));
      arr2.unshift(b.slice(start, lastIdx));
      lastIdx -= spSum;
    }

    const yuSum = Math.pow(10, spSum);
    for (let i = arr1.length - 1; i >= 0; i--) {
      temp = parseInt(arr1[i]) + parseInt(arr2[i]); // 求余值
      arr1[i] = temp % yuSum;
      // 前一位，进位值处理
      arr1[i - 1] = parseInt(arr1[i - 1]) + Math.floor(temp / yuSum);
    }
    var resStr = arr1.join('');
    return resStr[0] == '0' ? resStr.slice(1) : resStr;
  }
}
